home *** CD-ROM | disk | FTP | other *** search
/ NetNews Offline 2 / NetNews Offline Volume 2.iso / news / comp / lang / c-part1 / 3250 < prev    next >
Encoding:
Internet Message Format  |  1996-08-05  |  1.4 KB
  1. Path: news.mtu.edu!not-for-mail
  2. From: sjang@mtu.edu (Saurabh Jang)
  3. Newsgroups: comp.lang.c
  4. Subject: Re: Matrix Multiplication
  5. Date: 27 Jan 1996 02:24:20 -0500
  6. Organization: Michigan Technological University
  7. Message-ID: <4ecjv4$fn2@tamarack.cs.mtu.edu>
  8. References: <1996Jan22.110440@gamma.ntu.ac.sg>
  9. NNTP-Posting-Host: tamarack.cs.mtu.edu
  10. X-Newsreader: TIN [version 1.2 PL2]
  11.  
  12. Long (sz7212510@gamma.ntu.ac.sg) wrote:
  13. : Dear all,
  14.  
  15. : I would like to know whether anyone of you out there has better ways to
  16. : do matrix multiplication (optimised for speed) in C either than using
  17. : two nested for loops.
  18.  
  19. : Thanks.
  20.  
  21. : regds
  22. : Jos
  23.  
  24. Forget any rubbish such as Strassen's algorithm or Knuth's algorithms.
  25. these have very large constants and will buy you any thing only if
  26. you are dealing with HUGE matrices.
  27.  
  28. Consider optimizing for cache performance.
  29.  
  30. for ( i = 0; i < N; i++ )
  31.    for ( j = 0; j < N; j++ )
  32.    {
  33.       c[i][j] = 0.0;
  34.  
  35.       for ( k = 0; k < N; k++ )
  36.       {
  37.          c[i][j] = c[i][j] + a[i][k]*b[k][j];
  38.       }
  39.    }
  40.  
  41. increase in performance. Remember to initialize all the elems of c
  42. that you access in the innermost loop to zero before the innermost 
  43. loop. 
  44.  
  45. The reason for the improved performance lies in the reuse you get in
  46. the data cache from different loop orderings. 
  47.  
  48. -- 
  49. Saurabh Jang        e-mail:    sjang@cs.mtu.edu    
  50. MSCS Student        www   :    http://www.cs.mtu.edu/grads/Jang/Home.html
  51. Michigan Tech        work #: (906)487-2839
  52.